package ClassLib;

import javax.swing.text.rtf.RTFEditorKit;
import java.util.*;

public class libof202411_1 {


    /**
     * https://leetcode.cn/problems/subtree-of-another-tree/
     */
    class IsSubtreeSolution {
//        boolean ans =false;
//        String subtreeStr=null;
//        public boolean isSubtree(TreeNode root, TreeNode subRoot) {
//            subtreeStr=serialize(subRoot);
//            serialize(root);
//            return ans;
//        }
//        private String serialize(TreeNode node){
//            if(ans) return null;
//            String result;
//            if(node == null) result= "*";
//            else{
//                String left=serialize(node.left);
//                String right=serialize(node.right);
//                result= node.val + left + right;
//            }
//            if(result.equals(subtreeStr))
//                ans =true;
//            return  result;
//
//        }

        boolean ans =false;
        String subtreeStr=null;
        public boolean isSubtree(TreeNode root, TreeNode subRoot) {
            traverse(root,subRoot);
            return ans;
        }
        private void traverse(TreeNode node, TreeNode subRoot){
            if (ans) return;
            if (node == null && subRoot == null) {
                ans = true;
                return;
            }
            if(node==null||subRoot==null) return;
            if(isSame(node,subRoot)){
                ans =true;
            }
            traverse(node.left,subRoot);
            traverse(node.right,subRoot);
        }

        private boolean isSame(TreeNode node, TreeNode subRoot) {
            if (node == null && subRoot == null)  return true;
            if(node==null||subRoot==null) return false;
            if(node.val != subRoot.val) return false;
            return  isSame(node.left,subRoot.left)&&isSame(node.right,subRoot.right);
        }
    }

        //labuladong 题解
//public boolean isSubtree(TreeNode root, TreeNode subRoot) {
//    if (root == null) {
//        return subRoot == null;
//    }
//// 判断以 root 为根的⼆叉树是否和 subRoot 相同
//    if (isSameTree(root, subRoot)) {
//        return true;
//    }
//// 去左右⼦树中判断是否有和 subRoot 相同的⼦树
//    return isSubtree(root.left, subRoot) || isSubtree(root.right,
//            subRoot);
//}
//
//        public boolean isSameTree(TreeNode p, TreeNode q) {
//// 判断⼀对节点是否相同
//            if (p == null && q == null) {
//                return true;
//            }
//            if (p == null || q == null) {
//                return false;
//            }
//            if (p.val != q.val) {
//                return false;
//            }
//// 判断其他节点是否相同
//            return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
//        }
//    }


    /**https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/
     * @param root
     * @return
     */
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
      List<List<Integer>> result = new ArrayList<>();
        if(root==null) return result;
        Queue<TreeNode> queue = new LinkedList<>();
        boolean isRev=false;
        queue.offer(root);
        while (!queue.isEmpty()) {
            int sz = queue.size();
            LinkedList<Integer> list = new LinkedList<>();
            for (int i = 0; i < sz; i++) {
                TreeNode poll= queue.poll();
                if (isRev) list.addFirst(poll.val);
                else list.addLast(poll.val);
                if(poll.left!=null) queue.offer(poll.left);
                if(poll.right!=null) queue.offer(poll.right);
            }
            result.add(list);
            isRev=!isRev;
        }
        return result;
    }

    /**https://leetcode.cn/problems/even-odd-tree/
     * @param root
     * @return
     */
    public boolean isEvenOddTree(TreeNode root) {
        Queue<TreeNode> node= new LinkedList<>();
        node.offer(root);
        boolean isEven=true;
        while (!node.isEmpty()) {
            int sz = node.size();
            TreeNode pre=null;
            for (int i = 0; i < sz; i++) {
                TreeNode poll= node.poll();
                if(isEven){
                    if(poll.val%2==0) return false;
                    if(i>0&&poll.val<=pre.val) return false;
                }
                else{
                    if(poll.val%2!=0) return false;
                    if(i>0&&poll.val>=pre.val) return false;
                }
                if(poll.left!=null) node.offer(poll.left);
                if(poll.right!=null) node.offer(poll.right);
                pre=poll;
            }
            isEven=!isEven;
        }
        return true;
    }

    /**
     * https://leetcode.cn/problems/complete-binary-tree-inserter/
     */
    class CBTInserter {

        private final TreeNode root;
        private Queue<TreeNode> queue ;
        private Queue<TreeNode> temp;
        public CBTInserter(TreeNode root) {
            this.root = root;
            queue= new LinkedList<>();
            temp= new LinkedList<>();
            temp.offer(root);
            while (!temp.isEmpty()) {
                TreeNode poll= temp.poll();

                if(poll.left!=null){
                    temp.offer(poll.left);
                }
                if(poll.right!=null){
                    temp.offer(poll.right);
                }
                if(poll.left==null||poll.right==null){
                    queue.offer(poll);
                }
            }

        }

        public int insert(int val) {
            TreeNode node = queue.peek();
            TreeNode newNode = new TreeNode(val);
            if (node.left == null) {
                node.left = newNode;
            } else {
                node.right = newNode;
                queue.poll();
            }
            queue.offer(newNode);
           return node.val;
        }

        public TreeNode get_root() {
          return root;
        }
    }

    /**https://leetcode.cn/problems/check-completeness-of-a-binary-tree/
     * @param root
     * @return
     */
    public boolean isCompleteTree(TreeNode root) {
      Queue<TreeNode> queue = new LinkedList<>();
      queue.offer(root);
        boolean end=false;
      while (!queue.isEmpty()) {
          int sz = queue.size();
          for (int i = 0; i < sz; i++) {
              TreeNode poll= queue.poll();
              if(poll==null) end=true;
              else  {
                  if(end){
                      return false;
                  }
                  queue.offer(poll.left);
                  queue.offer(poll.right);
              }

          }
      }
      return true;
    }

    /** https://leetcode.cn/problems/time-needed-to-inform-all-employees/
     * 今天状态好差，需要调整一下，宝可梦不能再看了，明天再看吧
     * @param n
     * @param headID
     * @param manager
     * @param informTime
     * @return
     */
    public int numOfMinutes(int n, int headID, int[] manager, int[] informTime) {
        //存储这个人有哪些儿子,key 是-1的代表的是headid
        HashMap<Integer,HashSet<Integer>> map = new HashMap<>();
        for (int i = 0; i < manager.length; i++) {
            map.putIfAbsent(manager[i], new HashSet<>());
            map.get(manager[i]).add(i);
        }
        return dfs(map,informTime,-1);
    }

    private int dfs(HashMap<Integer, HashSet<Integer>> map, int[] informTime, int cur) {
       if(!map.containsKey(cur)){
          return 0;
       }
        HashSet<Integer> children = map.get(cur);
        int res=0;
        for (Integer child : children) {
          res=Math.max(res,dfs(map, informTime, child));
        }
        if(cur==-1) return res;
        return res+ informTime[cur];
    }

    /**https://leetcode.cn/problems/smallest-subtree-with-all-the-deepest-nodes/
     * @param root
     * @return
     */
//    Map<TreeNode,Integer> memo=new HashMap<>();
//    public TreeNode subtreeWithAllDeepest(TreeNode root) {
//       //最深节点的最小公共祖先
//        if(root==null) return null;
//        int leftMaxdepth= maxDepth(root.left);
//        int rightMaxdepth= maxDepth(root.right);
//        if(leftMaxdepth==rightMaxdepth) return root;
//        if(leftMaxdepth>rightMaxdepth) return subtreeWithAllDeepest(root.left);
//        return subtreeWithAllDeepest(root.right);
//    }
//
//    private int maxDepth(TreeNode root) {
//       if(root==null) return 0;
//       if(memo.containsKey(root)) return memo.get(root);
//       int ans= Math.max(maxDepth(root.left),maxDepth(root.right))+1;
//       memo.put(root,ans);
//       return ans;
//    }

    public TreeNode subtreeWithAllDeepest(TreeNode root) {
        //最深节点的最小公共祖先
        Object[] res=maxDepth(root);
        return (TreeNode) res[0];
    }

    private  Object[]  maxDepth(TreeNode root) {
        if(root==null) return new Object[]{null,0};
        Object[] left = maxDepth(root.left);
        Object[] right = maxDepth(root.right);
        if(left[1].equals(right[1]))
            return new Object[]{root,1+(Integer) (left[1])};
        Object[] res= (Integer)left[1]>(Integer) right[1]? left:right;
        res[1]=(Integer)res[1]+1;
        return res;
    }

    public void run() {
//       CBTInserter cbtInserter= new CBTInserter(new TreeNode(1,new TreeNode(2),null));
//       int ans= cbtInserter.insert(3);
//       ans= cbtInserter.insert(4);
        //var ans=numOfMinutes(6,2,new int[]{2,2,-1,2,2,2},new int[]{0,0,1,0,0,0});
        //var ans=numOfMinutes(1,0,new int[]{-1},new int[]{0});
        var ans=numOfMinutes(6,2,new int[]{2,2,-1,2,2,2},new int[]{0,0,1,0,0,0});
    }
}
